home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Monster Media 1996 #15
/
Monster Media Number 15 (Monster Media)(July 1996).ISO
/
math
/
hugemath.zip
/
HUGEMATH.DOC
< prev
next >
Wrap
Text File
|
1996-04-06
|
11KB
|
262 lines
/*
HUGEMATH DOCUMENT EXPLAINING BASIC USAGE
This program is basically a calculator which works with integers
These can be more or less as large as you want. The exe file supplied
has been compiled to accept integers up to about 500 digits each.
Some of the code may be difficult to read because it has been optimised
as far as possible. Many primality tests have also been implemented.
See the doc file for a description of usage.
This program was written by Paul Young, using Turbo C++.
I accept no responsibility for use or misuse of this program in any way.
This program is Public Domain.
It may be copied freely provided this notice is included.
This program may be used as a base or included in other programs
however these programs must also be Public Domain and no monetary gain
should be made from these. Help support Public Domain programming.
E-Mail P Young, 101716.3323@compuserve.com
*/
REGISTERS
---------
NB This program should be easily extendible using a C Compiler with the
routines already present.
You have four registers available for calculations - a,b,c and d.
Commands are entered directly to the program in the form of
command reg1,reg2/number
For example :
equ a,100 ;sets register a to 100.
add a,b ;adds register b to register a.
Some commands only have one argument for example
pri a ;prints register a to screen.
mul2 a ;a fast multiply of a by 2.
or no arguments for example
priall ;prints all register values to screen
The power of the program is its ability to handle very large numbers and
it has some powerful factorisation abilities.
COMMANDS
--------
All commands will be presented in the following way :
add reg1,reg2|num
means that the command 'add' takes the two arguments reg1 (for example 'a')
and reg2 (for example 'b') or a number instead of reg2 (for example 123456).
So valid commands are :
add d,c
add a,b
add a,124563554987698
Where further explanation is necessary this will follow later.
COMMAND SUMMARY
---------------
Command Action
--------------------------------------
add reg1,reg2|num ;reg1=reg1+reg2|num
div reg1,reg2|num ;reg1=reg1/reg2|num
mul reg1,reg2|num ;reg1=reg1*reg2|num
sub reg1,reg2|num ;reg1=reg1-reg2|num
mod reg1,reg2|num ;reg1=reg1 mod reg2|num
priall ;prints all regs to screen
pri reg1 ;prints value of reg1 to screen
inc reg1 ;reg1=reg1+1
dec reg1 ;reg1=reg1-1
equ reg1,reg2|num ;reg1=reg2|num
swap reg1,reg2 ;swaps values of reg1 and reg2
mul2 reg1 ;reg1=reg1*2 (faster than mul)
div2 reg1 ;reg1=reg1/2 (faster than div)
rep reg1,num ;reg1=num'th repunit
fib reg1,num ;reg1=num'th fibonacci number
smallfac reg1 ;removes small factors(<65536) of reg1
mer reg1,num ;reg1=num'th mersenne number
tdiv reg1,num ;trial divides reg1 by k*num+-1
gcd reg1,reg2|num ;reg1=gcd(reg1,reg2)
mprime reg1,num ;reg1=3*5*7*11*... for primes<num
root reg1,reg2|num ;reg1=squareroot(reg2|num)
psp reg1,num ;tests reg1 for num-pseudoprime
pollard reg1,num ;pollards factorisation
autopsp reg1,num ;tests reg1 for k-pseudoprime,k<num
monte reg1,num ;montecarlo factorisation
sequence reg1,num ;sequence factorisation
findwitness reg1,reg2|num ;used in prime testing
proveprime reg1,reg2 ;prime test
2pow reg1,num ;reg1=2^num (fast)
npow reg1,num ;reg1=reg1^num
factorial reg1,num ;reg1=num!
fermat reg1 ;fermats method of factorisation
quit ;quit the program
ADDITIONAL NOTES
----------------
When factorising large numbers ALWAYS use smallfac first. This will find
small factors very quickly and some methods assume small factors have been
removed. Other methods also run quicker the smaller the numbers present.
The next thing to do is really a psp test. This will not prove primality
but will show whether a number may be prime or is definitely composite. It
is also quite quick.
If a number is definitely composite then there are a number of choices open.
Remember that no program is a substitute for a good background knowledge of
number theory and with preparatory work a factorisation can usually be found
quicker.
With most of the methods below pressing a key will give some idea of how far
calculations have gone and pressing 'e' will stop it.
Tdiv
----
This is trial division. If nothing is known of the number then use tdiv a,6
assuming the number is in register 'a'. If factors are known to be of the
form 1024k+-1 say then use tdiv a,1024.
Pollard
-------
This can be a useful method and uses similar calculations to a psp test. It
will find a factor n quickly where n-1 has an 'easy' factorisation. The num
argument is the base, as for psp tests. Try first with 2 or 3 and if one of
these throws you out (doesn't happen very often but will with mersenne
numbers and a base of 2 then try another. Don't wait too long, if a factor
isn't found in a reasonable amount of time then you could have a long wait.
Fermat
------
This is a classic method found in most texts. It works best when both factors
are roughly the same size. Keypresses will take some time to register. I have
tried to speed the method up as far as possible with a 20-value sieve but
it's still not that good on large numbers.
Sequence
--------
Also known as Pollards rho method. Again a starting value is used. I've had
some good results with this one. Be patient. It works by looking for repeated
values in a sequence which will hopefully be fairly short with respect to one
of the factors. Best left rather than restarting with a new value. There is
room for optimisation here - see H Riesels 'Computer Methods of
Factorisation.' , Springer Verlag.
Monte Carlo
-----------
I leave it to you to try this but I've found it to be crap. Needs a decent
algorithm but I couldn't find any dissimilar to sequence which is better.
Proof Of Primality
------------------
I have implemented the n-1 method of proving primality as far as possible.
This is the proveprime command. The reg2 argument will be used to store any
residue. Normally this can prove a number to prime by factoring n-1 and
performing tests similar to psp tests. The problem comes when n-1 can't be
fully factored in a short space of time. Instead of leaving the program to
go off and do it's own thing I decided to dump the remainder of n-1 (the
unfactored part) in reg2 and leave it to the user. What you now have to do
is factor reg2 in some way and then use findwitness (witness is a bad name
here as it really means something else) to make the tests.
Most of the other commands should be straightforward so lets look at an
example now.
EXAMPLES
--------
What follows are two sessions using some of the above tests. User input
follows the Command> prompt. I have put comments in beginning with //.
Example 1
---------
// We will factorise the 89th Fibonacci number.
Command> fib a,89
Command> pri a
1779979416004714189
Command> smallfac a
Factor : 1069
Command> pri a
1665088321800481
Command> psp a,2
Pseudoprime
// Knowing this is a 2-pseudoprime we will try to prove primality
Command> proveprime a,b
.
.
. // We receive a lot of information about factors of a-1
. // and pseudoprimes. If the number is found to be composite
. // at any point then the test will end with a message to this effect.
.
N is prime
Command> // We have now completed this factorisation
// The final result is f(89) = 1069 * 1665088321800481
Example 2
---------
// This will be a more complicated example.
// This time we will factorise the 205th Fibonacci number.
Command> fib a,205
Command> pri a
3111581989804070186099320645726169127737705
Command> smallfac a
Factor : 5
Factor : 821
Factor : 2789
Factor : 59369
Command> pri a
4577831883071909637186705446981
Command> psp a,2
Composite
// We will have to search for a factor using one of the above methods
Command> pollard a,2 // purely arbitrary
Factor : 125598581 // found very quickly
// We will need to check that this is prime also since this is a general
// method of factorisation and only splits the number into two factors.
Command> equ c,125598581
Command> psp c,2
Pseudoprime
Command> proveprime c,d
.
. // loads of info again
.
.
N is prime // ok , we have another prime factor of f(205)
Command> pri a
36448117857891321536401 // this is what we have left
Command> psp a,2
Pseudoprime
Command> proveprime a,b
.
. // loads of info again
.
.
Test unfinished - residue left to be checked // oh dear
Command> pri b
740815403615677267 // this is the residue
// we need to factorise it and test each factor with the original 'a'
// using findwitness to complete the test.
Command> psp b,2
Composite
Command> pollard b,2
Factor : 110991193 // this took about 1 minute on a DX2
// Since this is only about 10000*10000 and we know that it has no
// factors less than 65536 since the original test couldn't factorise
// it, it must be prime. So theres no need to check but you can if you
// want to.
Command> findwitness a,110991193
witness 2 - checking pseudoprime
Pseudoprime
// This means we're in the clear. A witness was found and proved to be
// valid. If no witness is found (unlikely) the test fails and you will
// have to find some other way. The last line tells us this was ok. If
// this had said Composite then the original number would be composite.
Command> pri b
6674542219
// this is whats left from the unfinished test.
Command> proveprime b,2 // we'll try to show it's prime and finish it off
.
. // loads more info
.
.
N is prime // good
Command> findwitness a,b // going for the kill
witness 2 - checking pseudoprime
Pseudoprime
// well that's it all done.
// lets put that result together :
// f(205) = 5 * 821 * 2789 * 59369 * 125598581 * 36448117857891321536401
// and thats all there is to it.
// Happy prime hunting.
REQUEST
-------
Does anyone have details on the algorithm used in elliptic curve
factorisation ? or MPQS ? I would like a copy.
Please send to :
P Young, 101716.3323@compuserve.com